02/02/2021

Problema

  • Descrição:
    • Função:
      • Minimizar o número de pontos de acesso (Pa’s) na área de 800 x 800 metros que atendam à demanda de 475 clientes (Pd’s).
    • Restrições:
      • O alcance de cada Pa é um círculo com raio de 85 metros.
      • O número de Pa’s não deve ultrapassar 100.
      • A soma da demanda dos Pd’s cobertos por um dado Pa não deve ultrapassar 150 Mbps.

Espaço de busca

  • Escala:
    • Continua:
      • Existem infinitas coordenadas de possíveis localizações para os Pa’s tornando o problema computacionalmente insolúvel.
    • Discreta:
      • Considerando a área de 800 x 800 metros discretizada em inteiros, existem 640.000 possíveis localizações para os Pa’s tornando o problema computacionalmente solúvel.

Desenho do Algoritmo

  • Testes dos Espaços:
    • Espaços discretos menores que 8 x 8 não apresentaram solução ótima.
    • Espaços maiores que 150 x 150 apresentaram custo computacional muito elevado.
  • Implementação:
    • O algorítimo foi desenhado para escanear os espaços discretos de 8 x 8 até 150 x 150 na área de 800 x 800 com intervalos iguais entre os pontos.
    • Para ilustrar, foi considerado o espaço de 9 x 9, que representa 81 possíveis localizações para os Pa’s.

Interações do Algoritmo

  • Laço:
    • A cada iteração o algoritmo inspeciona cada coordenada do espaço discretizado de possíveis localizações dos Pa’s e determina o PA que cobre o maior número de Pd’s.
    • Se a condição de 150 Mbps não for violada, o índice do PA com maior cobertura de Pd’s é armazenado e esses Pd’s são removidos.
    • O algoritmo reinicia a busca do próximo PA que cobre mais Pd’s dentre os restantes.
  • Critério de Parada:
    • O algoritmo para quando cobre pelo menos 475 dos 500 Pd’s atendendo as restrições de consumo de banda e limite de Pa’s.

Primeira Iteração

  • O algoritmo conta o número de Pd’s cobertos por cada uma das 81 possíveis localizações para o 1º PA e soma os Mbps demandados.

  • O máximo de 202 Pd’s são cobertos pelo PA nas coordenadas (200, 200).

  • O total de 146 Mbps de demanda desses Pd’s não viola a condição de menor que 150 Mbps.

  • As coordenadas deste 1º PA são armazenadas.

  • Os 202 Pd’s cobertos por este PA são removidos por já estarem cobertos.

Segunda Iteração

  • O algoritmo realiza a mesma busca e contagem da primeira iteração, porém desconsiderando os Pd’s cobertos pelo 1º PA.

  • O máximo de 199 Pd’s são cobertos pelo PA nas coordenadas (600, 600).

  • O total de 141 Mbps de demanda destes Pd’s não viola a condição de menor que 150 Mbps.

  • Da mesma forma são armazenadas as coordenadas desse 2º PA.

  • Os 199 Pd’s cobertos por este PA também são removidos por já estarem cobertos.

Decima Sétima Iteração

  • O algoritmo para.

  • O resultado da busca retorna uma solução no mínimo local de 17 PA´s.

  • A condição de que 95% ou 475 do total de 500 pontos sejam cobertos é atendida.

  • A restrição de número de Pa’s menor que 100 é atendida.

  • A restrição de que a soma da demanda dos Pd’s cobertos por um Pa não exceda 150 Mbps é atendida.

  • As informações dos índices, número de Pd’s atendidos e total da demanda em Mbps de cada Pa podem ser recuperados.

Solução 9 x 9

Convergência

Custo Computacional

Solução 110 x 110

Método AHP

Objetivos Critérios e Optimizadores


Critério Máximo Mbps:

Critério Cobertura:

Critério Número de Pa’s:

Critério Unidade de Decisão:

Resultado do AHP:

Otimizador em Produção